Submitted herewith this present application (and on deposit in the United States Patent and Trademark Office) is a microfiche appendix comprising source code of a present embodiment of the present invention. There are 178 frames contained in 2 pages of microfiche.
For the purposes of the present invention, xe2x80x9cvirtual robotsxe2x80x9d (or xe2x80x9cBOTsxe2x80x9d) are software programs that interact and/or communicate with users (human, machine or otherwise) that take actions or make responses according to input from these users. BOTs are the subject of the co-pending and co-assigned parent application entitled xe2x80x9cMethods for Automatically Focusing the Attention of a Virtual Robot Interacting with Usersxe2x80x9d, filed Jun. 4, 1997, Ser. No. 08/868,713, and incorporated by reference in its entirety herein. A common use of such a BOT is as an interface to a web site wherein the administrator of that site has programmed the BOT to answer simple inquiries that are typically asked by visitors to the site. The above identified application discloses a method of creating BOTs according to xe2x80x9cscriptsxe2x80x9dxe2x80x94i.e. programs that are written in a very high level language that closely resembles a human natural language. These scripts embody a certain amount of information concerning the site that the administrator desires the BOT to communicate to a user during a connection session.
In such a BOT controlled by a script, it is the function of the BOT script to determine the response to any given user input. Ordinarily, a BOT script is written in such a way that, for each response it might make, it explicitly states a set of conditions (which may relate to both the input and the internal state of the BOT) that must be true in order for that response to be appropriate. Thus, for any particular input and internal BOT state, zero or more responses will be appropriate. These responses are said to xe2x80x9cmatchxe2x80x9d the input, although there is no requirement that the selection of responses is based on pattern-matching.
A BOT script can be written in such a way that at most one response will match any input. One way to achieve this is by requiring the conditions associated with the responses to be mutually exclusive, so that at most one response has a true condition for any input. Another way is to impose a fixed total ordering on any set of responses in the script that might conflictxe2x80x94for instance, by assigning a priority according to the order in which the responses appear in the script or by attaching explicit priority numbers to each response.
Such solutions are particularly difficult to implement in natural language systems, in which there are often a large number of rules in the script and an unbounded variety of probable inputs. If the conditions are made mutually exclusive, then the addition of a new rule may require modification of an arbitrary number of other rules. While if the conditions are kept in a fixed order, the addition of a new rule requires a complicated decision about where in the fixed order it belongs. Therefore, in designing a BOT script, it is useful to allow a particular input to be matched by more than one possible response.
If the BOT script allows more than one response to match an input, and does not provide any explicit total ordering on the possible responses, there are several ways in which the set of possible responses could be used. The BOT execution system might present all of the possible responses to the user, either in ordered or unordered form, or it might select one, or several, of the possible responses. In the case where the BOT execution system is either ordering the possible responses or selecting some subset of the responses, the execution system must have an automated way of deciding among the set of possible responses. One such mechanism is to xe2x80x9cfocusxe2x80x9d the attention of the BOT to a particular set of conversational categories, as discussed in the above-incorporated application.
However, there are many instances where a method based purely on the context of the conversation is insufficient. For instance, consider the following two inputs that might be given to a BOT: xe2x80x9cWhat is a bot?xe2x80x9d, xe2x80x9cWhat is a sales bot?xe2x80x9d. The first input might be handled in the BOT script by a condition that checks to see whether the input starts with the word xe2x80x9cwhatxe2x80x9d and contains the word xe2x80x9cbotxe2x80x9d, while the second input might be handled by a condition that checks to see whether the input starts with the word xe2x80x9cwhatxe2x80x9d and contains the words xe2x80x9csales botxe2x80x9d. Clearly both conditions are true for the input xe2x80x9cWhat is a sales bot?xe2x80x9d; but (presumably) the BOT should give the answer to the second condition regardless of the context of the question. Of course, in this case, the BOT author could resolve the problem by modifying the first condition so that it checks to see whether the starts with the word xe2x80x9cwhatxe2x80x9d, contains the word xe2x80x9cbotxe2x80x9d, and does not contain the word xe2x80x9csalesxe2x80x9d, but in general it is difficult and time-consuming for the BOT author to anticipate every possible such conflict between answers, and difficult to add to the script once written. Similarly, the BOT author could resolve the problem by insuring that the second condition is always tested before the first condition, but maintaining an ordering on all the possible conditions that might be added makes the BOT authoring task considerably more difficult.
Therefore, in the case where a BOT script provides conditions under which a response is appropriate, there is a need in the art for an automatic method of selecting a response from a number of possible responses such that the BOT author does not need to make the conditions mutually exclusive nor impose a fixed ordering on the conditions.
There is also a need for this mechanism to produce appropriate responses to both context-sensitive and context-independent inputs. For example, on an input such as xe2x80x9cWho is he?xe2x80x9d, the context of such an input is not entirely obvious. But, other inputs such as xe2x80x9cWho is the president of Neuromedia?xe2x80x9d, should elicit a unique response that is less dependent on the context of the statement. Thus, this mechanism should attempt to work equally well on both types of statements. In particular, there is a need to handle the problem of ambiguity that the pronouns inject into a conversation.
In addition, there is a need for this response selection mechanism to be efficient for large BOT scripts. As most BOTs are designed to handle queries from one to many simultaneous users, real-time performance is a practical consideration for such a mechanism.
The present invention meets these aforementioned needs by providing a variety of mechanisms for automatically and efficiently selecting a response from a number of possibilities. In one aspect of the present invention, in an automated interface program designed to interact and communicate with users, said program executing actions when a category among a set of predefined categories is activated, a method is disclosed for selecting a category given a situation or user input, the steps of said method comprising:
(a) defining a list of categories activatable by said program;
(b) for an input,
(i) identifying a first set of categories activated by said input;
(ii) selecting a second set of categories from said first set of activated categories based upon a metric, said metric computed based on the conditions located within each said activated category;
(iii) executing actions associated with said second set of categories.
In one aspect of the present invention, the metric disclosed in the selecting step above is an estimate of the appropriateness of the particular response included in an activated category. This estimate is currently based on the current input and the current state of the BOT upon said input.
In one aspect, the metric is a numeric value computed for each activated category, the value being based upon the frequency of matched words, partial words, symbols and the like found in the current input with words, partial words, symbols and the like found in the conditional clauses located within the category. Thus, as between two activated categories that could potentially respond to a given input, the metric acts as a filter to select that category that is xe2x80x9cmore appropriatexe2x80x9dxe2x80x94e.g. the category that may have more words matched in its conditional clause than the other category is likely to be xe2x80x9cmore appropriatexe2x80x9d.
In another aspect of the present invention, the metric may reflect the testing of a Boolean variable located in the category, the truth or falsity of said Boolean variable aiding in determining whether the category is selected or not. Some Boolean variables might be instantiated as a xe2x80x9cmemory attributexe2x80x9d that tests certain conditions based upon content-dependent aspects of the inputxe2x80x94e.g. a memory attribute might test for whether the input discusses some aspect of the cost of a product (e.g. xe2x80x9cwhat is the price?xe2x80x9d; xe2x80x9cwhat does it cost?xe2x80x9d; xe2x80x9chow much do I need to spend?xe2x80x9d). These memory attributes can thus be set; and may be persistent over the course of the conversation with the user. Other types of Boolean variables or conditions can be devised.
In another aspect of the present invention, a user-defined mechanism allows topics of conversation to be associated with a subject. A pronoun replacement mapping is additionally associated with the subject. Whenever a topic becomes active during the course of interaction with a user, the pronoun replacement mapping likewise becomes active. The effect of the mapping is such that whenever a pronoun is used by the user, such pronoun is replaced by a pre-defined object of conversation.
Other aspects of the category selection mechanism are disclosed in the below description when read in conjunction with the accompanying figures.